#include <time.h>
#include <stdlib.h>  // for srand

void sort(int arr[], int low, int high);
void swap(int arr[], int indexA, int indexB);

void sort(int arr[], int low, int high) {
    if (low >= high) {
        return;
    }
    int i = low, lt = low, gt = high;
    while (i <= gt) {
        if (arr[i] < arr[lt]) {
            swap(arr, lt++, i);
        } else if (arr[i] > arr[lt]) {
            swap(arr, i, gt--);
        } else {
            i++;
        }
    }
    sort(arr, low, lt - 1);
    sort(arr, gt + 1, high);
}

void swap(int arr[], int indexA, int indexB) {
    int tmp = arr[indexA];
    arr[indexA] = arr[indexB];
    arr[indexB] = tmp;
}